package algorithm

import (
	"fmt"
)

func maxSumOfSubArray(a []int) int {
	// 初始化最大和为数组的第一个元素
	maxSum := a[0]

	n := len(a)

	// 第 i 遍搜索从第 i 个元素开始往后搜索
	for i := 0; i < n; i++ {
		// sum用于记录从第 i 个元素到第 k 个元素的和，i <= k
		sum := 0

		for k := i; k < n; k++ {
			sum += a[k]
			if sum > maxSum {
				//找到一个比之前找到的最大值更大的连续子序列和
				maxSum = sum
			}
		}
	}

	return maxSum
}

func RunSubList() {
	a := []int{1, -5, 8, 3, -4, 15, -8}
	fmt.Println("max sum is:", maxSumOfSubArrayv2(a))
}

func maxSumOfSubArrayv2(a []int) int {
	maxSum := a[0]
	sum := a[0]

	for i := 1; i < len(a); i++ {
		sum += a[i]
		if sum < 0 { // 分界点，重新求和
			sum = 0
		} else {
			if sum > maxSum {
				maxSum = sum // 记录最大和
			}
		}
	}
	return maxSum
}
